// 3. 无重复字符的最长子串
var lengthOfLongestSubstring = function(s) {
    let left = 0, right = 0, res = 0;
    let window = {}
    while(right<s.length){
        let c = s[right];
        right++;
        window[c] = (window[c] || 0) + 1;
        while(window[c]>1){
            let d = s[left];
            left++;
            window[d] = window[d]-1;
        }
        res = Math.max(res, right-left);
    }
    return res;
};

// 5. 最长回文子串

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const length = s.length;
    if(length<2) return s;
    let res = '';
    for(let i = 0; i<length; i++){
        const s1 = palindrome(s, i, i);
        const s2 = palindrome(s, i, i+1);
        res = res.length > s1.length ? res: s1;
        res = res.length > s2.length ? res: s2;
    }
    return res;
};

function palindrome(s, left, right){
    while(left>=0 && right<s.length && s[left] === s[right]){
        left--;
        right++;
    }
    return s.substring(left+1, right);
}


// 14. 最长公共前缀
var longestCommonPrefix = function (strs) {
    const length = strs.length;
    if (length == 0) return '';
    if (length == 1) return strs[0];
    let res = strs[0];
    for (let i = 1; i < length; i++) {
        res = getSameStr(res, strs[i]);
        if (res.length == 0) break;
    }
    return res;
};

function getSameStr(a, b) {
    let res = '';
    for (let i = 0; i < a.length; i++) {
        if (a[i] === b[i]) res += a[i];
        else return res;
    }
    return res;
}

// 20 有效的括号
var isValid = function(s) {
    let map = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    }

    let array = [];
    for(let i = 0; i< s.length; i++){
        if(s[i] === '[' || s[i] === '{' || s[i] === '('){
            array.push(s[i]);
        } else {
            if(s[i] === map[array[array.length-1]]){
                array.pop()
            } else {
                return false;
            }
        }
    }
    return array.length > 0 ? false : true;
};

// 125 验证回文串
var isPalindrome = function(s) {
    if(s === ' ') return true;
    s = s.toLowerCase();
    let left = 0, right = s.length-1;
    while(left<=right){
        if(!isValid(s[left])){
            left++;
            continue;
        }
        if(!isValid(s[right])){
            right--;
            continue;
        }
        if(s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
};

function isValid(c){
    if((c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c<='9')) return true;
    return false;
}

// 151. 反转字符串中的单词
var reverseWords = function(s) {
    let res = [];
    let word = '';
    let left = 0, right = s.length-1;
    while(s[left] === ' '){
        left++;
    }
    while(s[right] === ' '){
        right--;
    }
    while(left<=right){
        if(s[left] === ' ' && word){
            res.unshift(word);
            word = '';
        } else if(s[left] !== ' '){
            word += s[left];
        }
        left++;
    }
    res.unshift(word);;
    return res.join(' ');
};

